package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-04
 */

/**
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 *
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 */
public class leetcode329 {
    private int m; //行
    private int n; //列
    private int ans = 0;
    private int[][] mat;
    private int[][] dir;
    public int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        mat = matrix;
        dir = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans,dfs(i,j));
            }
        }
        return ans;
    }

    public int dfs(int x,int y){
        if (dir[x][y]!=0) return dir[x][y];
        dir[x][y]++;

        for (int[] d : dirs) {
            int newX = x+d[0], newY = y+d[1];
            if (check(newX,newY) && mat[newX][newY]>mat[x][y])
                dir[x][y] = Math.max(dir[x][y],dfs(newX,newY)+1);
        }
        return dir[x][y];
    }

    public boolean check(int x,int y){
        return x>=0 && y>=0 && x<m && y<n;
    }
}
